# comun self hosted implementation: bytecode optimization library
# module prefix: o
#
# This module provides resources for performing automatic bytecode optimization.

~"cmn_bytecode.cmn"

# arg: n
# Removes n instrs from BC, starting with current instruction, also
# appropriately recalculating jump addrs.
CMN_oRemoveInstrs:
  ~16 0 ~0 $0 >16

  ~16
    $CMN_bCurrentInstr>_CMN_g2P1
    $CMN_bCurrentInstr>_CMN_g2P2
    $+_CMN_g2P2

    @@
      $_CMN_g2P2 $:_CMN_g2P1

      $_CMN_g2P2 !! ?
        !@
      .

      $>_CMN_g2P2
      $>_CMN_g2P1
    .
  ~0

  ~32
    $CMN_bCurrentInstrAddr # for return
    0 CMN_bCurrentInstrSetAddr
  ~0

  @@
    CMN_bCurrentInstrGet CMN_bInstrOpcode

    $0 !! ?
      ^
      !@
    .

    $0 CMN_bOPCODE_CAL = $1 CMN_bOPCODE_JIA = | $1 CMN_bOPCODE_JNA = |
    $1 CMN_bOPCODE_JMA = | >< ^ ?
      # instr uses addr

      ~32 CMN_bCurrentInstrGetConst32 $1 >= ? ~0
        # addr is beyond removed region => recompute

        $0 # n
        0 ~32 CMN_bCurrentInstrGetConst32 $1 - >0 ~0 # dist to removed start
        $1 $1 > ? >< . ^ # min of the two above (this is important to do!)

        @'
          CMN_bCurrentInstrDecrementConst
          --
        .
        ^
      .
    .

    CMN_bCurrentInstrShift
  .
  
  ^ # n

  CMN_bCurrentInstrSetAddr # consumes the addr pushed above
.

# Removes instrs from BC which have no effect, most importantly NOPs but also
# other instrs that do nothing. Modifies current instruction pointer.
CMN_oRemoveIneffective:
  ~32 0 ~0 CMN_bCurrentInstrSetAddr

  ~16 0 ~0
  CMN_bOPCODE_NOP 0 0 0 0 CMN_bMakeInstr >16 # for comparison
  
  @@
    CMN_bCurrentInstrGet !! ?
      !@
    .

    ~16 $CMN_bCurrentInstr>_CMN_g2P1 ~0
    0 # NOP count

    @@
      ~16 $0 $_CMN_g2P1 != ? ~0
        !@
      .

      ~16 $>_CMN_g2P1 ~0
 
      ++
    .
    
    # TODO: more types of do-nothing instrs

    ?'
      $0 CMN_oRemoveInstrs # remove NOPs
    ;
      CMN_bCurrentInstrShift
    .
 
    ^ # NOP count
  .

  ~16 ^ ~0 # comparison NOP
.

# In BC replaces func calls by their code if it's not longer than the call.
# Modifies CMN_bCurrentInstr.
CMN_oInlineFuncs:
  ~32 0 ~0 CMN_bCurrentInstrSetAddr

  @@
    CMN_bCurrentInstrGet CMN_bInstrOpcode 

    $0 CMN_bOPCODE_END = ?
      ^
      !@
    .

    CMN_bOPCODE_CAL = ?
      CMN_bCurrentInstrGetConstBits 4 / # call len

      ~32 $CMN_bCurrentInstrAddr ~0 # to return later

      CMN_bCurrentInstrGetConst32 CMN_bCurrentInstrSetAddr

      ~16 $CMN_bCurrentInstr>_CMN_g2P1 ~0

      0 # function len

      @@
        CMN_bCurrentInstrGet CMN_bInstrOpcode CMN_bOPCODE_RET = ?
          !@
        .

        CMN_bCurrentInstrShift
        ++
      .

      CMN_bCurrentInstrSetAddr # restore previous addr

      $1 $1 >= 0 ~16 $CMN_bCurrentInstr=_CMN_g2P1 >0 ~0 & ?
        # function len <= call len and non-recursive call
        ><
        ~16 $CMN_bCurrentInstr>_CMN_g2P2 ~0

        @' # fill call with NOPs
          ~16 0 ~0 CMN_bOPCODE_NOP >16 
          ~16 $:_CMN_g2P2 $>_CMN_g2P2 ~0
          --
        .
        ^

        ~16 $CMN_bCurrentInstr>_CMN_g2P2 ~0
        
        @' # copy the code
          ~16
            $_CMN_g2P1 $:_CMN_g2P2
            $>_CMN_g2P1
            $>_CMN_g2P2
          ~0
          --
        .
        ^
      ; 
        ^ ^
      .
    .

    CMN_bCurrentInstrShift
  .
.

# In BC replaces code of unused funcs with NOPs (except for debug instrs).
# Modifies CMN_bCurrentInstr
CMN_oBlankUnusedFuncs:
  ~32 0 ~0 CMN_bCurrentInstrSetAddr

  @@
    CMN_bCurrentInstrGet CMN_bInstrOpcode

    $0 CMN_bOPCODE_END = ?
      ^
      !@
    .

    CMN_bOPCODE_DES = CMN_bCurrentInstrGetConst CMN_bDES_FUNDEF = & ?
      ~32 $CMN_bCurrentInstrAddr ~0 # for return

      @@ # find func end addr
        CMN_bCurrentInstrGet CMN_bInstrOpcode CMN_bOPCODE_RET = ?
          !@
        .

        CMN_bCurrentInstrShift
      .

      ~32
        $CMN_bCurrentInstrAddr # push the end addr
        $1 CMN_bCurrentInstrSetAddr # get back
      ~0

      # now look for the first call of the func:

      ~32 0 ~0 CMN_bCurrentInstrSetAddr
      0 # call found?

      @@
        CMN_bCurrentInstrGet CMN_bInstrOpcode

        $0 CMN_bOPCODE_END = ?
          ^
          !@
        .

        CMN_bOPCODE_CAL = ?
          ~32
            CMN_bCurrentInstrGetConst32 $0

            # stack now: addrStart addrEnd callAddr callAddr

            $2 <= >< $3 >= & ? # jump between start and end?
              ~0 ^ 1 ~32 # call found
              !@
            .
          ~0
        .
    
        CMN_bCurrentInstrShift
      .

      !! ? # no call found? => blank
        ~32 $1 ~0 CMN_bCurrentInstrSetAddr

        1 @
          CMN_bCurrentInstrGet CMN_bInstrOpcode CMN_bOPCODE_DES =
          CMN_bCurrentInstrGetConst
          $0 CMN_bDES_NEWLINE =
          $1 CMN_bDES_NEWFILE = |
          >< CMN_bDES_ENDFILE = | & !! ? # isn't debug instr?
            ~16 0 ~0 CMN_bOPCODE_NOP >16 ~16 $:CMN_bCurrentInstr ~0
          . 

          CMN_bCurrentInstrShift
          0 ~32 $CMN_bCurrentInstrAddr $1 <= >0 ~0
        .
      .

      ~32 ^ ~0 # func end addr
      CMN_bCurrentInstrSetAddr # get back
    .

    CMN_bCurrentInstrShift
  .
.

# arg: i1 i2 a1 a2 b1 b2
# ret: i1b i2b succ
# Tries to replace two instrs with optimized ones, returns 1 if this was done,
# else 0. If instrs i1 and i2 have the same TE, then if i1 equals a1 and i2
# equals a2, disregarding TE, i1b/i2b will be b1/b2 with TE of i1/i2 (otherwise
# i1b/i2b will be left as i1/i2).
_CMN_oOptimizeInstrPair:
  $5 CMN_bInstrTypeEnv $5 CMN_bInstrTypeEnv = ? # same TE?
    $5 +x3fff & $4 +x3fff & = $5 +x3fff & $4 +x3fff & = & ? # match pattern?
      $:2 $:2
      +x3fff & $2 +xc000 & | $:2
      +x3fff & $2 +xc000 & | $:2
      1
      !.
    .
  .
    
  ^ ^ ^ ^ 0
.

# Replaces some patterns in BC with shorter/usually faster ones. Modifies
# CMN_bCurrentInstr.
CMN_oReplaceInstrs:
  ~32 0 CMN_bCurrentInstrSetAddr ~0

  @@
    ~16
      $CMN_bCurrentInstr

      ?'
        $>CMN_bCurrentInstr
        $CMN_bCurrentInstr
        $<CMN_bCurrentInstr
      ;
        0
      .

      ><
      ~0 0 ~16 >0
      ~0 0 ~16 >0
    ~0

    # now we have two consecutive instrs in TE 0

    $1 $1 && !! ?
      ^ ^ # instrs
      !@
    .

    4 $:_CMN_gV1

    1 @ # for various ICs
      $_CMN_gV1 -- $:_CMN_gV1

      # multiply => shift:
      CMN_bOPCODE_CON 0 1   1 $_CMN_gV1 |<     0 CMN_bMakeInstr
      CMN_bOPCODE_MUX 0 0   0                  0 CMN_bMakeInstr
      CMN_bOPCODE_CON 0 0   1 $_CMN_gV1 |<     0 CMN_bMakeInstr
      CMN_bOPCODE_SLC 0 0   $_CMN_gV1          0 CMN_bMakeInstr
      _CMN_oOptimizeInstrPair

      ? !@ .

      # divide => shift:
      CMN_bOPCODE_CON 0 1   1 $_CMN_gV1 |<     0 CMN_bMakeInstr
      CMN_bOPCODE_DIX 0 0   0                  0 CMN_bMakeInstr
      CMN_bOPCODE_CON 0 0   1 $_CMN_gV1 |<     0 CMN_bMakeInstr
      CMN_bOPCODE_SRC 0 0   $_CMN_gV1          0 CMN_bMakeInstr
      _CMN_oOptimizeInstrPair

      ? !@ .

      # modulo => shift:
      CMN_bOPCODE_CON 0 1   1 $_CMN_gV1 |<          0 CMN_bMakeInstr
      CMN_bOPCODE_MOX 0 0   0                       0 CMN_bMakeInstr
      CMN_bOPCODE_CON 0 0   1 $_CMN_gV1 |<          0 CMN_bMakeInstr
      CMN_bOPCODE_BAC 0 0  -1 $_CMN_gV1 |< ! +xf &  0 CMN_bMakeInstr
      _CMN_oOptimizeInstrPair

      ? !@ .

      # merge pops:
      CMN_bOPCODE_POP 0 0   1 $_CMN_gV1 |< --  0 CMN_bMakeInstr
      CMN_bOPCODE_POP 0 0   1 $_CMN_gV1 |< --  0 CMN_bMakeInstr
      CMN_bOPCODE_POP 0 0   2 $_CMN_gV1 |< --  0 CMN_bMakeInstr
      CMN_bOPCODE_NOP 0 0   0                  0 CMN_bMakeInstr
      _CMN_oOptimizeInstrPair

      !! $_CMN_gV1 * # multiply by return value
    .

    # write the potentially modified instrs back:
    ~16 0 ~0 >16
    ~16 0 ~0 >16
    ~16 $:CMN_bCurrentInstr ~0
    CMN_bCurrentInstrShift
    ~16 $:CMN_bCurrentInstr ~0
  .
.

# arg: n
# ret:
# Applies all common optimizations to BC in n iterations, recomputes checksum.
CMN_oOptimize:
  # TODO: repeat all several times

  @'
    CMN_oRemoveIneffective
    CMN_oReplaceInstrs

    CMN_oInlineFuncs
    CMN_oBlankUnusedFuncs
    CMN_oRemoveIneffective

    --
  .
  ^

# TODO: fix (on test_big)
# CMN_oBlankUnusedFuncs crashes C comun
# CMN_oRemoveInstrs crashes self comun but not C comun

  ~16
    CMN_bChecksum
    $CMN_bBytecode>_CMN_g2P1
    $>_CMN_g2P1 $>_CMN_g2P1 $:_CMN_g2P1
  ~0
.
